STARKs memo
Convert computation to AIR (Algebraic Intermediate Representation)
R1CSの一般化
R1CSはAIRの特殊なケース
それぞれのconstraintはproduct of two linear forms
AIRはより大きい次数でも可能
IP (Interactive Proofs)
PCP (Probabilistically Checkable Proofs)
IOP (Interactive Oracle Proofs)
IPとPCP両方の一般化
IPの性質によりproverとverifierはinteractiveにやり取りするが、PCPの性質によりverifierはproverのmessageを読み取る必要はなく、ランダムにクエリする。つまり、クエリ量が多いほどsoundnessの確率が高まる。
proverのscalability
PoC
ZK-PCP, ZK-IOP
interactiveにやり取りするmessageをハッシュ関数などで秘匿化
(1) transparency
(2) universality
(3) confidentiality
(4) post-quantum security
(5) proof/argument of knowledge
(6) scalable verification
ZK-STIK (Scalable Transparent IOP of Knowlege)
(7) fully scalable : proverとverifierのrunning timeがscalable
FRI (Fast Reed-Solomn (RS) IOP of Proximity (IOPP))
ProverがassignmentをVerfieirに送り、それが全てのconstraintsに満たすか検証する
計算の実行時間とassignmentは同じサイズになってしまう。
つまり、verificationがスケールしない
ProverがPCPを送り、そのPCPでverifierがconstantなポイントを検証する。
PCP自体にerror correcting encodingをする必要があり、encoded PCPがsatisfying assignmentより大きくなってしまう。つまり、計算の実行時間より大きくなってしまう。
Verifierがargumenrを送り、そのhash digestを返して、それを元にProverがconstantにピックアップして、VerifeirがPCPを検証する。
argument あるいは CS proofs
十分なsoudnessのためにはconstantsがかなり大きくなってしまう。
snarkは加法準同型暗号でlow-degree polyであることを保障して、starkはPCPでlow-degree polyであることを保障。
Berlekamp-Welch algorithm
Reed-solomon encodingのデコーダー。つまり、誤りデータを含んでいるデータ群からオリジナルの多項式を復元するアルゴリズム。
例えば、オリジナルのデータを4個に分割して、3次式を復元したことを考える。
4つの点では、誤りを見つけることができない。
5つの点を持っていれば、どれか１つが誤っている、と探知することはできる。
6つの点を持っていれば、1つの誤りを正すことができる、あるいは、2つの誤りを探知することができる。
よって、十分なextra pointを持っていればどの点が間違っているか分かる。
DPM (DNA profile match problem)
ある時間tのfingerprintコミットメント$ cm_tとprofileのコミットメント$ cm_pとともにdatabase$ Dに一致検索をかけて$ aが返ってくる。($ a : “no match”, “partial match”, or “full match”)
public input : $ cm_t, cm_p, a
private input : DNA profile database $ D', individual DNA profile $ p'
Computation $ Cがsatisfyすべき3つの条件
Dのコミットメントがcm_tと一致するか
pのコミットメントがcm_pと一致するか
Dの中からpに対する一致検索のoutputが$ aと一致するか
STARK vs Ligero
stark
verifierのスケーリング
大きなcircuitsに対するproof size
Ligero
prover computation time
sha256数個程度の比較的小さなcircuitに対するproof size
Arithmetization
arithmetizationとは、計算問題を代数学問題へ還元すること。
つまり、有限体上のlow-degree多項式に落とし込む。ここでいうlow-degreeとは、有限体の位数に比べて十分小さいということ。
Register-based encoding
rowがwでそれぞれのタイムステップの計算状態
colmunがc*nである全てのcycleをトラックしたalgebraicレジスタ
従来の方法だと全てのtraceに対して１つのReed-Solomonを実行するアプローチなので、多項式の次元がn*c*wにdをかけてlocal mapが必要だった。
今回のアプローチでは、それぞれのレジスタに対してseperateしたReed-Solomonを使うのでn*c*dの次数がw個あるようになる。トレードオフとして、w個に対してそれぞれRPT問題を解決しなければならないように見えるが、全てのwに対するランダム線形和を適用することで（IOPモデルのランダムネスとinteractive）により確率的に1回のRPT問題を解くだけでOKに。
LDE (Low degree exetension)
input sizeのnが大きくなってしまうと多項式の次元数も大きくなてしまう。
Main Methods
AIR -> APR -> RPT
CI statementのinstance: boundary & transition constraints (x) : witness定義の状態を満たすためのcurrent step -> next step遷移relation
計算状態遷移のtranstion relation
inputやoutputのboundary constraints
$ (i, j, a) = (cycle, register, machine state)
constraints -> 多項式（quadraticじゃない一般化）
witness: 計算のvalid execution (w) : それぞれのstepごとの正しい状態
execution trace: 計算のboundaryとtransitionそれぞれのconstraintsに基づくマシンstate関数のシークエンス。つまり、全てのcycleに対するそれぞれのレジスタを多項式で表現したシークエンス。
boundary constraintsを満たす。つまり、 全てのboundary constraintsに対して、 $ w_j(i) = a -> レジスタごとのwitness 関数において、あるcycleを入れるとboundary constraintsを満たすmachine stateを返す。
そのmachine stateをconstraintsに入れるとzeroを返し、circuit (monotone boolean circuit)に通すとTRUEを返す。このようなwitnessが正当となる。
procress
xとwのAIRからスタート。
execution traceの状態は全て、シーケンスの要素として表現。
transiton relationはexecution traceのcurrent -> nextを表す変数による多項式セットで表現。
AIRのマシンstate(witness)をaffine graphのノードに配置し、edgeで連続的な状態が結び付けられる。-> APR
algebraにより制限されたマシン状態のgraph構築。-> algebraic placement and routing
-> APR instance/witness pairへの還元
AIR: w -> states of the executuon trace are represented by sequences of elements in a finite field.
x -> the transiton relation is specified by a set of polynomials over variables representing the "current" and "next" step of the execution trace.
APR: w -> states of the execution trace are "placed" on nodes of an affine graph
(x -> consecutive states are connected by an edge in that graph)
BAIR += PAIR
要は、tinyRAMのmemory consistencyの考え方と同じ。
memoryを必要とする計算の場合はPAIR(permuted algebraic intermediate representation)のrelationを導入し、計算量をT^2 -> TlogTにするためにpermutedする。
ALI (algebratic linking IOP) protocol
step3 . APR representionがRPT(Reed
FRI
次数Dの多項式に対して、D個以下の点で確かに多項式上にあることをrandam oracleで確率的に証明する。
Fiat-Shamir ヒューリスティックでnon-interactiveにすることも可能。
AIR (Algebraic Intermediate Representation)
constraint systemの一般化。
BAIR = binary AIR
計算のtranstion relationがzeroになるようなAIRシステム
以下のパラメタを減らすことがここでの目標。
degree: 全てのconstraintのAir中での最大次数 (d)
width (state size): stateを表すために必要な変数の数(w)
system size: constraintの数(s)
cycle count: 計算を実行するのに必要なcycle数 (circuit depthの下限）
input要素数nに対するcycle数
つまり、c*nが全体のcycle数
binary fieldで
why
arithmetic operationsが効率的
例えば足し算がxorと対応
FRI3rdにalgebratic structureが必要 (fieldの理由やん）
APR (algebraic placement and routing)
AIR -> APRのreductionはdeterministicなのでperfectなcompletness and soudness
-> back-to-back De Bruijn routing
ALI (Algebraic Linking Interactive Oracle Proof)
1-roundのIOPによるverifierのrandomnessに多くのconstraintsが結び付けられる。
APRからRPTへの変換
prover timeのmain bottleneckはFFT、inv-FFTのコスト - 複数点での多項式評価
つまり、proverがinterpolate、評価しなければならない多項式の最大次数。
starkでは $ d^{max} = n * c * dに。つまり、input要素あたりのcycle数
これにより、ランダムなAIRの線形和である１つのconstraintに還元することが可能に。
RPT( Reed-solomon proximity testing) problem
LDE (Low Degree Extension)
APC (Authentication Path Complexity)とCC (Communication Complexity) の最小化
PCP
検証者が長さO(r)の乱数列を使って証明のO(q)ビットを検索して検証できる場合にこの証明システムをPCP(r, q)であるという。
検証者は検索する必要があるため証明は検証者が指定した書き方で用意される。
つまり、検証者は乱数の助けと多項式時間計算能力により証明の一部を検索システムでみて「答えがYESである」ことを納得する。
正しい証明ならどこを読んでも正しい。偽証明だと確率1/2以上で検証者は誤りを発見する。
要は、多項式時間で解ける問題はP=PCP(1,1)=PCP(1, logn)
NP問題では判定がYESであることに対して、多項式長の証明が与えられて、これを全部読めれば検証により解くことができるので、NP <- PCP(1, poly)(n))。
また、NP=PCP(logn, 1)。つまり、少しだけ乱数の助けを借りて、証明の定数ビットを見るだけでNP問題が解ける。 -> 定数ビットの知識だと検証者はYes or NOは判断できても実際の解を構成することはできない。
https://gyazo.com/eb723945e47a9a931ed3ec23d7218756
ある異なる２つの関数が交わる点はせいぜいmin(degree)個になるので、degreeがdomain sizeよりも十分に小さければランダムに選んだとしても、一致する点になる確率は限りなく小さい。
C(P(X))とQ'(X)D(X)それぞれ10^7で違う＝一致するのはmax10^7。
なので10^9でランダムピックアップすれば一致してしまうのは99%。
また、プログラムのexecution traceにおけるconstraint polynomialを考えると、（ここでは1つずつのインクリメントを考えると）レジスタは1つだけになり、
$ C(X) := X_{next}-X_{curr} - 1
となる。
なので、検証者のクエリは$ f(x_0), f(x_0+1), g(x_0)を行えばOK.
STARKのZKを加えるために、従来の1M個の点のリストに加え、ランダムに10個程度の点を加え、10^6+10-degreeの多項式を復元し、x_0のランダムには、1~10^9ではなく、10^6+1~10^9を用いることでexecution traceを秘匿化することができる。
input
input num
round constants (length = 64) -> iteration over steps i.e. steps mod round_constans
steps
(output)
trace constraints
A(x) = A(x - 1) ** 3 + W(x)
(( P(x * subroot) = P(x) ** 3 + K(x) ))
M
boundary constraints
A(0) = input num
A(last_step) = output num
witness
state registers
mimc state
loop counter
FRI(Fast Reed-Solomon Interactive Oracle Proofs of Proximity)
IOP
merkle treeを使ったlong PCPをproverがコミット。
ランダムなクエリとmerkle inclusion pathで検証。
transacripts stark-dex